#include <iostream>
#include <stdlib.h>

using namespace std;

template <typename T>
void show(T in[],int left,int right){
    for(int i=left;i<=right;i++){
        cout<<in[i]<<" ";
    }
    cout<<endl;
}
/*
template <typename T>
void QuickSort(T in[],int left,int right){
    if(left>right){
        return;
    }
    int privot=left+(rand()%(right-left+1));
    cout<<"privot:"<<privot<<",num:"<<in[privot]<<endl;
    T tmp=in[privot];
    swap(in[left],in[privot]);
    int i=left+1;
    int j=right;
    while(i<=j){
        while(in[i]<tmp){
            i++;
        }
        while(in[j]>tmp){
            j--;
        }
        //show(in,left,right);
        if(i<=j){
            swap(in[i],in[j]);
        }
        //show(in,left,right);
    }
    swap(in[left],in[j]);
    show(in,left,right);
    QuickSort(in,left,j-1);
    QuickSort(in,j+1,right);
}
// privot = 5
// 5 0 1 3 8 4 9 2 7 6
// 5 0 1 3 2 4 9 8 7 6 
*/

template <typename T>
int partition(T in[],int left,int right){
    int rand_pos=rand()%(right-left+1)+left;
    swap(in[left],in[rand_pos]);
    int pos=left;
    for(int i=left+1;i<=right;i++){
        if(in[i]<in[pos]){
            swap(in[i],in[pos]);
            pos++;
        }
    }
    return pos;
}
// 1 0 5 3 8 4 9 2 7 6 选取下标2 即in[2]=5 
// 5 0 1 3 8 4 9 2 7 6 i=1,pos=0 开始状态
// 0 5 1 3 8 4 9 2 7 6 i=1,pos=1
// 0 1 5 3 8 4 9 2 7 6 i=2,pos=2
// 0 1 3 5 8 4 9 2 7 6 i=3,pos=3
// 0 1 3 4 8 5 9 2 7 6 i=5,pos=4
// 0 1 3 4 2 5 9 8 7 6 i=7,pos=5
// 0 1 3 4 2 5

template <typename T>
void QuickSort(T in[],int left,int right){
    if(left<right){
        int pivot=partition(in,left,right);
        QuickSort(in,left,pivot-1);
        QuickSort(in,pivot,right);
    }
}

int main(){
    int a[]={1,0,5,3,8,4,9,2,7,6};
    QuickSort(a,0,9);
    show(a,0,9);
    return 0;
}